recent updates: ------------------------------------------------

-----------------------------------------------------
2024-10-02 : here is my new hardest,small,uniquely Hamiltonian graph.
It has 1120 vertices , 1960 edges and exactly one Hamiltonian cycle.
It is made of 140 "x8"s , connected with each other randomly
at their 4 outer vertices. An X8 is a C8 with additional edges 1-5 and 4-8 ;
the outer vertices are 1,3,6,8 .

-----------------------------------------------------
2024-04-30 : hard Hamiltonian Cycle Benchmarks
here is my currently hardest
uniquely Hamiltonian randomized xor-8 graph
where the generated exact-cover-problem and its SAT-instance
have also only one solution , (which is the Hamiltonian cycle).
http://magictour.free.fr/992.hcp
It has 992 vertices and 1736 edges, which is close to the
phase-transition for this type of graphs.

and here is its SAT-conversion :
http://magictour.free.fr/992.sat
it has 620 variables and 496 exactly-one-clauses
with 4-6 literals , 2480 exactly-one-literals in total.
This is then converted to normal .cnf-sat with the
standard=pairwise method.

clasp 3.3.5 needs 2 hours to find the solution
and 7 hours to confirm that there is only one solution.
On one thread of a Ryzen-9 computer with 5GHz and 128GB RAM
and with 5 other threads also being busy.
You can use clasp in Ubuntu after
sudo apt install gringo
(with internet connection and during German business hours)

kissat 3.1 needs 3 hours to find the solution and
6 hours to confirm that it's unique.

for every 80 additional vertices the required computing
time increases nearly 5-fold.

2024-05-01 another such 992-instance was found
no such graph was found yet with 1000 vertices,
despite one core-week of search

08,09030,32988,22456,
11,13840,23436,

seconds needed with kissat 3.1 to find the solution
seconds needed with kissat 3.1 to confirm that there is only one solution
seconds needed with clasp 3.3.5 to find the solution
seconds needed with clasp 3.3.5 to confirm that there is only one solution
(default CLPs)
clasp is faster in computing all solutions and in small instances
kissat is faster to find a solution in large instances (>500 variables=outer edges)

you can nicely encode these problems in clingo but just running clasp
on the sat-encodings was faster.
I also tried the "bitwise" encoding of at-most-one (AMO) clauses
this gives fewer cnf-clauses but gave no running time improvement.

-----------------------------------------


2024-04-14 here is a C-program to generate symmetric 8-part magic knight tours
on 4m*4n rectangles for m,n>1 :
4ssymkt
and a file with these tours upto size 32*32 :
sy32
part 1: m*n*2 visited cells
part 2: m*n*2 visited cells
part 3: horizontal reflections of part 1 visited in reverse order
part 4: horizontal reflections of part 2 visited in reverse order
parts 5-8 : 180 degree rotations of parts 1-4 visited in same order
I assume that there are no symmetric magic knight tours on
boards of size (4m+2)*n



2023-11-12
an SSD with all 1658420855433 closed 8x8 knight's tours is now available
One tour per symmetry-class, to be exact.
Compressed with 7zip in 41790 files , 3TB in total
Decompressed they contain one tour per line of 33 Bytes
1 Byte for 2 consecutive of the 8 directions.
Decoding+format-converting+analysing software to be included
and uploaded+updated later.



2023-11-12
for updates on the examination of general Hamiltonian Cycle
solvers and benchmarks see :
https://knighttours.createaforum.com/general-hamiltonian-cycles-problem/



2023-04-26
I enumerated the open 8x8 tours with the program
http://magictour.free.fr/ptourgl.c
which counts Hamiltonian cycles in a graph.
It was compiled under Ubuntu with
gcc ptourgl.c -o ptourgl
and run as ./ptourgl knig8x8p.ad1
If you can improve the program, make it faster or simpler
or easier to understand, I'd like to hear about it.

For the 8x8 open tours I used the 67-vertex-reordering
as given in the adjacency-matrix
http://magictour.free.fr/knig8x8p.ad1
The reordering was done under windows with the program
https://magictour.free.fr/reorder1.c
The calculation took 131 hours under Ubuntu-Linux on one core
of a 2012 laptop with a 1TB SSD.
It sorted big files with pathstructures on SSD at each
step=vertex-addition.
The maximum filesize was 94GB at step 48.
It encoded 2 digits into one byte, the program can currently
handle 12 different paths in the border-region.The maximum
that occurred was 10(?)
The maximum number different path-structures was 2163004549 at step 39.

The final result was 9795914085489952 Hamiltonian cycles in the
chosen graph, which are the undirected open knight's tours.
It matches the result of Alex Chernov from 2014,
without having to split the task into the 136 start-end combinations.
https://oeis.org/A165134
http://alex-black.ru/article.php?content=141

I also calculated the number of undirected 7x8 and 7x9 open knight's tours :
there are 20666425060328 and 5806424327506000 of them.
It took 3.5 and 9 hours.
https://oeis.org/A306283
The closed 8x8 tours were calculated in 4 hours.
My updated enumeration file from 2005 :
http://magictour.free.fr/enum2
for a description of the method see :
Pettersen thesis



Mar.2023 Here is a program to find 4-symmetric magic 2-knight's tours (2kts) :
http://magictour.free.fr/hamp4n.c
Some of them can be converted to 1kts with the "rolling pin" method
or can be extended to magic 1kts by adding a 4xn magic "linker-" 3kt


Feb.2023 for 8x10 magic tours (and other things) see this thread: 8x10
register to the phpbb forum to discuss and contribute ! a more computational and mathematical forum is here : knighttours

Dec.2022
Yann Denef found 11194 magic 8x8 2-knight-tours
2-kt


Apr.2021 it's much faster to generate knight's tours by subchain-reversals (why didn't I notice that earlier ...)


Sep.2020
Yann Denef has a program to find a closed 8x8 knight's tour by enumeration-index !
yd
His new version finds all closed tours in 5.1 days on a 6-core-Ryzen-5 .


May.2020
Yann Denef independently confirms the closed 8x8-calculation,
with the 41790 ranges running for 7.4 days on a Ryzen 5, 1600X, Six-Core



Apr.,May.2020
Awani Kumar sent emails about Magic Tours on
10xN,8x12,6x16,4x4x6,4x6x8,6x20
I haven't yet checked them



Jan.2020

I found a 132-pages thesis by Andrew Chalaturnyk from 2008 about a
fast algorithm for knight's tours using multiple paths
http://combinatorialmath.ca/G&G/chalaturnykthesis.pdf
the program seems to be available through their "groups and graphs" package
"not available for Linux and Windows" , and apparently discontinued, though
It is an improvement of an algorithm from 1992, however using multiple
paths, where you don't know the move-number yet, seems not suitable for
searching magic tours. But it should work for my project to store all
8x8 closed tours ... if it were easily available to me...
Anyway, I realized that there is no point in storing all closed 8x8 knight's tours
on a harddrive since you can better generate them on the fly, when needed.
(Although not fast enough with my current program and hardware.)

Jan.2020

before creating and storing the 1.7 trillion closed 8x8 knight's tours
I created and stored the 6x8 tours, including open ones, on a 1TB HD

Jan.2020

I'm trying to extend the 140 magic 8x8 knight's tours
to 12x12 and beyond by adding a "braid" around them,
as shown here on page 63.
That gave these 491 magic 12x12 tours ,
looking like this
They could easily be extended to 882 16x16 tours and beyond.
Here is a 1000*1000 magic knight's tour, visited squares at move 1,...,1000000
the squares are numbered 0,...,999999




Jan.2020
George Jelliss makes 12 downloadable pdfs from his
Knight's Tour Notes available here:
ktn
This is a lot of material about the theory and history
of knight's tours and similar things , much more than on his webpage
Here is the list of contents in one text-file :
ktn.txt

Jan.2020

George Jelliss makes 12 downloadable pdfs from his
Knight's Tour Notes available here:
ktn
This is a lot of material about the theory and history
of knight's tours and similar things , much more than on his webpage
Here is the list of contents in one text-file :
ktn.txt

Nov.2019
Yann Denef improved his program ,
it now finds all magic knight's tours in 22hours
on a Ryzen 5 1600X with 6 cores at 3.6GHz.
his results file
his description
his nodecounts compared to ours



Aug.2019
I counted 8x8 closed knight's tours with Fei Lu's program for
the 41790-corner-ranges on 8-12 threads of a Ryzen 1700x in 16 days.
The final number matches the earlier reported value.
The tours were created and node-counts collected but they are
not yet printed and stored. That will probably be done the
coming winter taking ~2 months. In compressed form they
should fit on a 6TB harddrive.

see 8x8 (to be updated)


Jul.2019
Awani Kumar's 2018 paper on (magic) tours on rectangular boards : rect.mag.


Awani Kumar's 2017 paper on magic 4x4x4 tours : 4x4x4
file with the 216 magic tours numbered as magic cubes : 4x4x4b.txt
file with the 10368 rotations+reflections numbered as tours : 4x4x4b.kt


Sep.2013
Alex Chernov counted open 8x8 knight's tours
Chernov
(in Russian)
enum
will be updated

Jan.2009 Awani Kumar has enumerated over 3000 semi-magic knight's tours
on 10x10 board achieving 75% magic ratio, the highest on any
singly-even board till date.
Here is such a tour: 10x10




21.Nov.2008 Awani Kumar has enumerated 208 magic tours of knight in 4x4x4x4 hyperspace.
Sum of all the rows,columns,pillars and files is 514
4x4x4x4,base 4




17.Oct.2008 Awani Kumar has further extended the knight's tour into fifth dimension.
He has constructed a knight's magic tour in a 4x4x4x4x4 hyperspace, the largest till date.
Sum of all the rows,columns,pillars,files and poles is 2050. 4x4x4x4x4




27.Sept.2008 Awani Kumar has extended the knight's tour into fourth dimension.
He has constructed a knight's magic tour in a 4x4x4x4 hyperspace.
Sum of all the rows,columns,pillars and files is 514. 4x4x4x4



27.March 2008: Awani Kumar's larger knight's tour magic squares:
1) 12x12 2) 16x16,diagonal 3) 14x14 semi-magic



16.December 2007: Awani Kumar's larger knight's tour magic cubes:
1) 8x8x8 2) 8x8x8,triagonal 3) 8x8x8,triagonal 4) 12x12x12,triagonal
cube properties


15.October 2007: And now the 4x4x4 magic tours !
4x4x4

all cubes with magic-cube-analysis:
54 magic 4x4x4 tours




04.August 2007: Awani Kumar sent me a list of 76 16x16 magic
knight's tours , the 2 diagonals are also magic.
16x16




01.July 2007: Awani Kumar sent me a list of 1306 12x12 (semi-) magic
knight's tours !
When you have further 12x12 semi-magic knight's tours, please send them so they can be included.
12x12




28.April 2007: Awani Kumar found a magic 3-dimensional 8*8*8 Knight's Tour !
3d-magic tour




1st Nov.2005: Dan Thomasson illustrates the SMKTs
and groups them by halftours and other similarities :
Dan's pictures



15th May 2004: Yann Denef redid the whole calculation with a slightly
different method in 8.22*10^15 CPU cycles, 30% faster than our program !
see his webpages at (in French) :
10th August 2004: Yann Denef improved his program, by avoiding symmetries,
now he needs 5.5*10^15 cycles = 67% of his 1st version = 46% of our program
Yann Denef's pages


08th November 2004: I put a new c-program here to illustrate the
algorithm how to find Hamilton paths ("tours") in undirected
graphs:
hampath.c
20th January 2005: enumerating knight's tours on rectangular boards
counts


in Deutsch : magische Springertouren


text version : text-version
Computing Magic Knight Tours


August 5th 2003 : we have finished . All 136 ranges have been checked.
There are 140 magic knight's tours on the chessboard and none of these
is diagonally magic.


This project was to enumerate all the magic knight's tours
("MKTs") on an 8*8 chessboard.
A knight's tour (or knight tour) is an n*n matrix a(n,n) containing
the numbers 1 to n*n exactly once and consecutive numbers are a
chessknight's move apart :
a(u,v)=1+a(x,y) implies (u-x)*(u-x)+(v-y)*(v-y) = 5.
A knight's tour a(,) is magic, iff all rows and columns of a(,)
sum to (n*n+1)*n/2, the magic constant of the MKT.
A knight's tour a(,) is called diagonally magic, iff it is magic
and the two main diagonals sum to the magic constant too.
This project showed that no diagonally magic knight tour exists on the 8*8 board
A knight's tour a(,) is called pandiagonal iff all the 2*n broken
diagonals add to the magic constant too.
that means : SUM {j=1..n} of a(j,(i+j) mod n) = n*n+1)*n/2 for i=0..n-1
and SUM {j=1..n} of a(j,(i-j) mod n) = n*n+1)*n/2 for i=0..n-1

Sometimes MKTs are call "semimagic" and diagonally magic tours
are called magic. But we follow Jelliss' nomenclature,
indicating that the two main diagonals are not so important.
In the following the assume n=8.

Prior to this project 2128 MKTs were known,from 133
symmetry-classes (see below). 112 new MKTs were found during
this project from 7 symmetry classes.

for a complete list see :
http://www.mayhematics.com/t/mc.htm

you can download a complete list of 2240 MKTs, 140 symmetry classes
and 108 geometry-classes in computer-readable form here : (674KB)
mkts

Example of a MKT:

8- 01 30 47 52 05 28 43 54
7- 48 51 02 29 44 53 06 27
6- 31 46 49 04 25 08 55 42
5- 50 03 32 45 56 41 26 07
4- 33 62 15 20 09 24 39 58
3- 16 19 34 61 40 57 10 23
2- 63 14 17 36 21 12 59 38
1- 18 35 64 13 60 37 22 11
  a b c d e f g h
Beverley,1848 a8-c1

this is the first found MKT.

The start-square is the square containing "1" and the end-square
is the square containing "64". These are a8 and c1 in the example above.

For a history of MKT-search see: http://www.mayhematics.com/t/1d.htm

Every MKT gives 15 other MKTs in the same symmetry-class by rotation, reflection and reverse numbering.
A tour is called closed, if startsquare and endsquare are a knight's
move apart, otherwise it is called open.

A closed MKT sometimes gives new MKTs in the same geometry-class, by adding a constant c to each entry:
b(x,y) = ( (a(x,y)-1+c) modulo 64 ) +1

there are 2240 MKTs from 140 symmetry classes and
108 geometry-classes,

1232 open MKTs from 77 symmetry classes and 77 geometry-classes, and

1008 closed MKTs from 63 symmetry classes and 31 geometry-classes.

We estimated that an exhaustive computer-search for all MKTs would
take less than 6 months on a 2GHz computer.
Indeed, after JC Meyrignac had optimized his program a lot
only 2 months were needed !

the program can be downloaded here :
MagicTour program

The program runs at idle priority on Windows. You can stop the program,

but the current computation is lost (there is no save/load function).

The program is heavily optimized, the source-code is long and hard
to understand. Here is a C-program by Fei Lu with explanations:
knight.c

We are also interested in general Hamilton-path-programs to eventually extend this search to other boards and pieces later.

April 27th 2003: First version of the web site.
May 25th 2003: Second version of the web site
(improvement-suggestions are welcome)
June 19th 2003: Third version of the web site
June 16th 2003: computation of ranges had started
June 18th 2003: Success: after 2 days of computation, Hugues Mackay
had found the first new magic knight's tour !

6 other new MKTs were found during the project.
here are the 7 new MKTs :


8- 59 30 35 24 57 22 15 18
7- 36 25 58 29 16 19 56 21
6- 31 60 27 34 23 54 17 14
5- 26 37 32 49 28 13 20 55
4- 39 04 61 12 33 48 53 10
3- 62 01 38 07 50 11 44 47
2- 05 40 03 64 45 42 09 52
1- 02 63 06 41 08 51 46 43
  a b c d e f g h
Mackay/Meyrignac/Stertenbrink
2003/06/18 b3-d2

8- 11 46 51 40 09 38 31 34
7- 52 41 10 45 32 35 08 37
6- 47 12 43 50 39 06 33 30
5- 42 53 48 01 44 29 36 07
4- 55 20 13 28 49 64 05 26
3- 14 17 54 23 02 27 60 63
2- 21 56 19 16 61 58 25 04
1- 18 15 22 57 24 03 62 59
  a b c d e f g h
Jelliss
2003/06/19 d5-f4

8- 34 51 32 13 62 37 20 11
7- 15 30 35 50 19 12 61 38
6- 52 33 14 31 36 63 10 21
5- 29 16 49 44 05 18 39 60
4- 48 53 04 17 64 43 22 09
3- 01 28 45 56 25 06 59 40
2- 54 47 26 03 42 57 08 23
1- 27 02 55 46 07 24 41 58
  a b c d e f g h
Mackay/Meyrignac/Stertenbrink
2003/06/21 a3-e4

8- 18 39 64 09 58 41 24 07
7- 63 10 17 40 23 08 57 42
6- 38 19 36 61 16 59 06 25
5- 11 62 13 20 33 22 43 56
4- 50 37 32 35 60 15 26 05
3- 31 12 49 14 21 34 55 44
2- 48 51 02 29 46 53 04 27
1- 01 30 47 52 03 28 45 54
  a b c d e f g h
Mackay/Meyrignac/Stertenbrink
2003/06/24 a1-c8

8- 54 13 50 23 10 19 44 47
7- 51 24 53 12 45 48 09 18
6- 14 55 22 49 20 11 46 43
5- 25 52 15 64 37 42 17 08
4- 56 01 26 21 16 63 36 41
3- 27 30 59 04 33 38 07 62
2- 02 57 32 29 60 05 40 35
1- 31 28 03 58 39 34 61 06
  a b c d e f g h
Mackay/Meyrignac/Stertenbrink
2003/07/01 b4-d5

8- 54 45 18 23 42 51 12 15
7- 19 24 53 44 13 16 41 50
6- 46 55 22 17 52 43 14 11
5- 25 20 47 64 05 10 49 40
4- 56 01 26 21 48 63 36 09
3- 27 30 59 04 33 06 39 62
2- 02 57 32 29 60 37 08 35
1- 31 28 03 58 07 34 61 38
  a b c d e f g h
Mackay/Meyrignac/Stertenbrink
2003/07/01 b4-d5

8- 34 23 42 47 18 31 38 27
7- 43 48 33 24 37 28 17 30
6- 22 35 46 41 32 19 26 39
5- 49 44 21 36 25 40 29 16
4- 06 53 04 45 20 61 12 59
3- 01 50 07 56 09 58 15 64
2- 54 05 52 03 62 13 60 11
1- 51 02 55 08 57 10 63 14
  a b c d e f g h
Mackay/Meyrignac/Stertenbrink
2003/08/01 a3-h3

here is the complete list of the computation of the 136 cases/ranges, the solutions and people who computated that range : ranges

Thanks to
Hugues Mackay, Dan Thomasson, Guenter Stertenbrink, Tom Marlow, NovaTec,
Hendrik Tyman, Werner Schauer, Thilo Rottmann, GrafZahl, Euler
for computing ranges and helping to finish the project.
Special thanks to Hugues Mackay, who computed more than 100 ranges alone !
Not to forget JC Meyrignac for writing the fast program and helping to set up this webpage

as of August,05.,2003 136 ranges have been checked
5305279.08 seconds = 61.40 days of computation time were needed
CPUs went through 11_945038 Gigacycles = 138.25 days with 1GHz
52_280100_180652 knightmoves were done, that's 228.5 CPU-cycles per move (=node)
between 7.0e10 and 3.1e12 nodes per range, average 3.8e11, deviation 5.4e11

nodecounts of the different ranges : nodecounts
graphics of the complexity of the ranges : NODES2.GIF
computer-readable list of all MKTs : (674KB) mkts.txt
picture of the 108 geometry-classes: MKTS108B.GIF
graphics of the start and end squares (courtesy to Harold Cataquet): reachable squares
our page on latin torus leaper tours : latin torus-leaper-tours
our oncoming(?) project to (re)count all 8*8 knight tours : computing knight tours

here is the mathworld article about the project : mathworld article

other pages:
Jelliss, knight tour notes
[ most comprehensive webpage about knight tours ! ]
Velucchi, knight-links
[ special site devoted to knight tour links ]
Friedel,F.:"The Knight's Tour."
[ entertaining and curious ]
mathworld-MagicTour:
[ introduction,definitions,examples,links
note, that E.Weisstein at Mathworld uses different definitions than we and Jelliss:
"magic tour" (Mathworld) = "diagonally magic tour" (Jelliss)
"semimagic tour" (Mathworld) = "magic tour" (Jelliss)
"semimagic tour" (Jelliss) = [only the rows add to the magic constant]


some links to German sites : Heise Artikel

[ article about this project with discussion ]
A.Conrad
[ how to find a tour on large boards ]
Dan Thomasson
[ the same, with another method, nice graphics ]
PDF-paper by Lee
[ about fast algorithms to count knight tours ]

Visitor numberVisitor since May 1st 2003.
[return to top]
last updated: November 26th 2019 created 2003 by Guenter Stertenbrink and Jean Charles Meyrignac mailto:sterten@posteo.de